package leetcode.code1914;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution1withdebug implements IDebug {

	public int[][] rotateGrid(int[][] grid, int k) {
		int m = grid.length, n = grid[0].length;
		// 最大转移步数
		int min = Math.min(m, n);
		int max = Math.max(m, n);// 最多走max - 1 步
		// dp[x][y] = z 意味着 x位置走y步到 z
		int[][] dpMove2 = new int[m * n][max];
		int[] dpMoveMax = new int[m * n];
		int min2 = min >> 1;
		// 起始位置[0,0],起始位置转移方向右下[1,1],填装dp方向向下[1,0],填装步数m - 1,层控制min2,待填装dp,列宽,最大步长
		fillDp(0, 0, 1, 1, 1, 0, m - 1, min2, dpMove2, n, dpMoveMax);
		fillDp(m - 1, 0, -1, 1, 0, 1, n - 1, min2, dpMove2, n, dpMoveMax);
		fillDp(m - 1, n - 1, -1, -1, -1, 0, m - 1, min2, dpMove2, n, dpMoveMax);
		fillDp(0, n - 1, 1, -1, 0, -1, n - 1, min2, dpMove2, n, dpMoveMax);
//		for (int i = 0; i < dpMove2.length; i++) {
//			for (int j = 1; j < dpMove2[0].length; j++) {
//				int x = i / n, y = i % n;
//				int x2 = dpMove2[i][j] / n, y2 = dpMove2[i][j] % n;
//				System.out.println(x + "," + y + " " + j + " 步走到" + x2 + "," + y2 + " 最大转移步数" + dpMoveMax[i]);
//			}
//		}
		int[][] ans = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				int index = this.index(i, j, n);
				int move = k;
				while (move > 0) {
					int moveMax = dpMoveMax[index];
					if (moveMax >= move) {
						int move2 = dpMove2[index][move];
						int x2 = move2 / n, y2 = move2 % n;
						ans[x2][y2] = cur;
					} else {
						index = dpMove2[index][moveMax];
					}
					move -= moveMax;
				}
			}
		}
		H.print(ans);
		return ans;
	}

	public void magic(int m, int n) {
		int min = Math.min(m, n);
		int max = Math.max(m, n);// 最多走max - 1 步
		// dp[x][y] = z 意味着 x位置走y步到 z
		int[][] dpMove2 = new int[m * n][max];
		int[] dpMoveMax = new int[m * n];
		int min2 = min >> 1;
		// 起始位置[0,0],起始位置转移[1,1],填装dp方向向下[1,0],填装步数,层控制min2,待填装dp,列宽
		fillDp(0, 0, 1, 1, 1, 0, m - 1, min2, dpMove2, n, dpMoveMax);
		fillDp(m - 1, 0, -1, 1, 0, 1, n - 1, min2, dpMove2, n, dpMoveMax);
		fillDp(m - 1, n - 1, -1, -1, -1, 0, m - 1, min2, dpMove2, n, dpMoveMax);
		fillDp(0, n - 1, 1, -1, 0, -1, n - 1, min2, dpMove2, n, dpMoveMax);
	}

	private void fillDp(int startx, int starty, int startx2, int starty2, int dpx, int dpy, int step, int size,
			int[][] dp, int n, int[] dpMoveMax) {
		if (size == 0) {
			return;
		}
		for (int i = 0; i < step; i++) {
			int myStartx = startx + dpx * i, myStarty = starty + dpy * i;
			int index = this.index(myStartx, myStarty, n);
			int MoveMax = step - i;
			dpMoveMax[index] = MoveMax;
			dp[index][0] = index;// 没用
			for (int s = 1; s <= MoveMax; s++) {
				int index2 = this.index(myStartx + dpx * s, myStarty + dpy * s, n);
				dp[index][s] = index2;
			}
		}
		this.fillDp(startx + startx2, starty + starty2, startx2, starty2, dpx, dpy, step - 2, size - 1, dp, n,
				dpMoveMax);
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

//	private int[] info(int m, int n, int i, int j, int k) {
//		int u = i, l = j, r = n - j - 1, d = m - i - 1;
//		int min = Math.min(Math.min(u, d), Math.min(l, r));
//		int less = min * 2;
//		int round = (m + n) * 2 - 4 - less * 4;
//		k %= round;
//		int[] size = new int[] { n - less, m - less, n - less, m - less };
//		int[] rests = new int[] {};
//		int direction = 0;// 0,1,2,3 左下右上
//		if (min == u) {
//			direction = min == l ? 1 : 0;
//		} else if (min == l) {
//			direction = min == d ? 2 : 1;
//		} else if (min == d) {
//			direction = min == r ? 3 : 2;
//		} else {
//			direction = min == u ? 0 : 3;
//		}
//		int L = min, R = n - min - 1;
//		int U = min, D = m - min - 1;
//		if (direction == 0) {
//
//		}
//		return new int[] { direction, round, less };
//	}

	@Override
	public void debug4() {
		this.rotateGrid(H.str2array1("[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]"), 2);
//		this.rotateGrid(H.str2array1("[[40,10],[30,20]]"), 1);

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution1withdebug so = new Solution1withdebug();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
